class Solution{
public:
  typedef struct _NODE{
    int r;
    int c;

    _NODE(int rr, int cc) : r(rr), c(cc){};

    _NODE operator+(const _NODE &right) const{

      return _NODE(this->r + right.r, this->c + right.c);
    }

    bool operator<(const _NODE &right) const{

      return this->r < right.r && this->c < right.c;
    }

    bool operator>=(const _NODE &right) const{

      return this->r >= right.r && this->c >= right.c;
    }
  } NODE;

  bool exist(vector<vector<char>> &board, string word){

    vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
    for(int i = 0; i < board.size(); i++){
      for(int j = 0; j < board[0].size(); j++){
        if(board[i][j] == word[0]){
          visited[i][j] = true;
          if(dfs(NODE(i, j), board, visited, word.c_str() + 1)){
            return true;
          }
          visited[i][j] = false;
        }
      }
    }
    return false;
  }

  bool dfs(const NODE now, vector<vector<char>> &board, vector<vector<bool>> &visited, const char *word){

    static const vector<NODE> dir{
            NODE(-1, 0), NODE(1, 0), NODE(0, -1), NODE(0, 1)
    };
    if(*word == '\0'){
      return true;
    }
    int R = board.size();
    int C = board[0].size();
    for(auto &d : dir){
      NODE next = now + d;
      if(next >= NODE(0, 0) && next < NODE(R, C) && !visited[next.r][next.c] && board[next.r][next.c] == *word){
        visited[next.r][next.c] = true;
        if(dfs(next, board, visited, word + 1)){
          return true;
        }
        visited[next.r][next.c] = false;
      }
    }
    return false;
  }
};